package main

import "fmt"

// 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
// 状态转移方程 dp[l, r] = (s[l] == s[r] and (l - r >= -2 or dp[l + 1, r - 1]))
// 长度为n https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/
// 可以先画一张状态转移表
func longestPalindrome(s string) string {
	size := len(s)
	if size <= 1 {
		return s
	}
	lp := 1
	lps := s[0:1]
	dp := make([][]bool, size, size)
	for i := 0; i < size; i++ {
		dp[i] = make([]bool, size)
	}
	for r := 1; r < size; r++ {
		for l := 0; l < r; l++ {
			if s[l] == s[r] && (r-l <= 2 || dp[l+1][r-1]) {
				dp[l][r] = true
				if r-l+1 > lp {
					lp = r - l + 1
					lps = s[l : r+1]
				}
			}
		}
	}
	return lps
}

func main() {
	ret := longestPalindrome("eabcb")
	fmt.Println(ret)
}
